package codetop.microsoft.T15;

import java.util.*;

/**
 * @Author: 18362
 * @Create: 2022-08-13 22:02:25 星期六
 */
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length < 3)
            return result;
        Arrays.sort(nums);
        for (int i=0; i<nums.length; ++i) {
            if (i > 0 && nums[i] == nums[i-1])
                continue;
            List<List<Integer>> res = twoSum(nums, i + 1, -nums[i]);
            for (List<Integer> r : res) {
                r.add(nums[i]);
                result.add(r);
            }
        }
        return result;
    }

    private List<List<Integer>> twoSum(int[] nums, int start, int target) {
        List<List<Integer>> result = new ArrayList<>();
        int left = start, right = nums.length - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            int leftBase = nums[left], rightBase = nums[right];
            if (sum == target) {
                List<Integer> res = new ArrayList<>();
                res.add(nums[right]);
                res.add(nums[left]);
                result.add(res);
                while (left < right && nums[left] == leftBase)
                    left++;
                while (left < right && nums[right] == rightBase)
                    right--;
            } else if (sum < target) {
                while (left < right && nums[left] == leftBase)
                    left++;
            } else {
                while (left < right && nums[right] == rightBase)
                    right--;
            }
        }
        return result;
    }
}